import java.util.Arrays;
import java.util.PriorityQueue;

public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap() {
        this.elem=new int[10];
    }

    //初始化
    public void init(int[] array) {
        for(int i=0;i<array.length;i++) {
            elem[i]=array[i];
            usedSize++;
        }
    }

    //把elem数组中的数据调整为一个大根堆
    public void createBigHeap() {
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--) {
            siftDown(parent,usedSize);
        }
    }
    public void siftDown(int parent,int end) {
        int child=2*parent+1;//这里计算的是左孩子的下标
        while(child<end) {  //不能取等,usedSize取不到
            if(child+1<end && elem[child]<elem[child+1]) { //if语句的俩条件不能互换位置
                child++;
            }
            //child下标就是左右孩子中最大的那个
            if(elem[child]>elem[parent]) {
                //交换
                swap(child,parent);
                parent=child;//parent走到刚才交换的孩子节点
                child=2*parent+1;//孩子节点走到新的孩子节点位置
            }else {
                break;
            }
        }
    }
    private void swap(int i,int j) {
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }

    public void offer(int val) {
        if(isFull()) {
            elem= Arrays.copyOf(elem, elem.length*2);
        }
        elem[usedSize++]=val;
        siftUp(usedSize-1);
    }
    public boolean isFull() {
        return elem.length==usedSize;
    }
    public void siftUp(int child) {
        int parent=(child-1)/2;
        while(parent>=0) {
            if(elem[child]>elem[parent]) {
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }

    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        int old = elem[0];
        swap(0, usedSize - 1);
        usedSize--;
        siftDown(0, usedSize);
        return old;
    }
    public boolean isEmpty() {
        return usedSize==0;
    }

    /**
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> minHeap=new PriorityQueue<>();
        for(int i=0;i<arr.length;i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for(int i=0;i<k;i++) {
            int val=minHeap.poll();
            tmp[i]=val;
        }
        return tmp;
    }

    public int[] smallestK2(int[] arr, int k) {
        int[] tmp=new int[k];
        if(k==0) return tmp;
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new IntCmp());
        //1. 把前k个元素放入堆中
        for(int i=0;i<k;i++) {
            maxHeap.offer(arr[i]);
        }
        //2. 遍历剩下的n-k个元素
        for(int i=k;i<arr.length;i++) {
            int val=maxHeap.peek();
            if(val>arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for(int i=k-1;i>=0;i--) {
            tmp[i]=maxHeap.poll();
        }
        return tmp;
    }


    //堆排序
    public void heapSort() {
        int endIndex=usedSize-1;
        while(endIndex>0) {
            swap(0,endIndex);
            siftDown(0,endIndex);
            endIndex--;
        }
    }

}
